package 中等.哈希表;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * 给你一个字符串数组 words。
 * 一步操作中，你可以交换字符串 words[i] 的任意两个偶数下标对应的字符
 * 或任意两个奇数下标对应的字符。
 * 对两个字符串 words[i] 和 words[j] 而言，如果经过任意次数的操作，
 * words[i] == words[j] ，那么这两个字符串是 特殊等价 的。
 * 例如，words[i] = "zzxy" 和 words[j] = "xyzz" 是一对 特殊等价 字符串，
 * 因为可以按 "zzxy" -> "xzzy" -> "xyzz" 的操作路径使 words[i] == words[j] 。
 * 现在规定，words 的 一组特殊等价字符串 就是 words 的一个同时满足下述条件的非空子集：
 * 该组中的每一对字符串都是 特殊等价 的
 * 该组字符串已经涵盖了该类别中的所有特殊等价字符串，容量达到理论上的最大值
 * （也就是说，如果一个字符串不在该组中，那么这个字符串就 不会 与该组内任何字符串特殊等价）
 * 返回 words 中 特殊等价字符串组 的数量。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/groups-of-special-equivalent-strings
 */
public class 特殊等价字符串组_893 {

    public static void main(String[] args) {

        System.out.println(numSpecialEquivGroups(new String[]{"abc", "acb", "bac", "bca", "cab", "cba"}));

    }

    /**
     * 排序+哈希表
     * 奇数位和偶数位的字符互不干扰，将奇数位字符排序和偶数位
     * 字符排序之后拼接起来，一组特殊等价字符串这样得到的字符串
     * 一定是相同的
     */
    public static int numSpecialEquivGroups(String[] words) {
        Set<String> set = new HashSet<>();

        // 防止频繁创建数组
        char[] odd = new char[(words[0].length()) / 2];
        char[] even = new char[(words[0].length() + 1) / 2];
        for (String word : words) {

            int oddIdx = 0, evenIdx = 0;
            for (int i = 0; i < word.length(); i++) {
                if (i % 2 == 0) {
                    even[evenIdx] = word.charAt(i);
                    evenIdx++;
                } else {
                    odd[oddIdx] = word.charAt(i);
                    oddIdx++;
                }
            }
            Arrays.sort(odd);
            Arrays.sort(even);
            set.add(new StringBuilder().append(odd).append(even).toString());
        }

        return set.size();
    }

}
